﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ProjectEulerSolutions
{
    /*
     * n! means n × (n − 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

     * 
     * 
     * */
    class Problem20
    {
        public static string Calculate()
        {
            double digitTest = 1;

            int limit = 100;

            for (int i = 1; i <= limit; i++)
                digitTest *= i;


            int numOfDigits = (int) Math.Ceiling(Math.Log10(digitTest)) + 1; //+1 zasvaki slučaj ;)

            int[] digits = new int[numOfDigits];

            digits[0] = 1;

            for (int i = 1; i <= limit; i++)
            {
                int overflow = 0;
                for (int j = 0; j < numOfDigits; j++)
                {
                    int num = digits[j] * i;
                    digits[j] = (num + overflow) % 10 ;
                    overflow = (num + overflow) / 10;
                }
            }

            int sum = digits.Sum();

            return sum.ToString();
        }
    }
}
